//
// Created by daiyizheng on 2022/3/26.
//
#include <algorithm>
#include <queue>
using namespace std;
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

/*
      23(1)
     /    \
34(2=2*1) 21(3=2*1+1)
 给每个节点编号 ， 父亲节点编号*2 + 1（left+0, right +1）
 */
typedef unsigned long long ULL;
int widthOfBinaryTree(TreeNode* root) {
    if(!root)return 0;
    queue<pair<TreeNode*, ULL>> qe;
    qe.push(make_pair(root, 1));
    int maxWith = 0;
    while (!qe.empty()){
        int size = qe.size();
        ULL  startNo = 0;
        ULL endNo = 0;
        for (int i = 0; i < size; i++) {
            pair<TreeNode*, ULL> s = qe.front();
            qe.pop();

            TreeNode *currNode = s.first;
            ULL seqNo = s.second;

            if (i==0)startNo = seqNo;
            if(i==size-1) endNo = seqNo;
            if (currNode->left) qe.push(make_pair(currNode->left, 2 * seqNo));
            if (currNode->right) qe.push(make_pair(currNode->right, 2 * seqNo + 1));
        }
        maxWith = max(maxWith, (int)(endNo-startNo+1));
    }
    return maxWith;
}


// DFS
int postorder(TreeNode* node, int currLevel, ULL seqNo, vector<ULL>& start, vector<ULL>& end);
int widthOfBinaryTree2(TreeNode* root) {
    vector<ULL> start, end;
    return postorder(root, 0, 1, start, end);
}

int postorder(TreeNode* node, int currLevel, ULL seqNo, vector<ULL>& start, vector<ULL>& end) {
    if (node == nullptr) return 0;

    if (start.size() == currLevel) {
        start.push_back(seqNo);
        end.push_back(seqNo);
    } else {
        end[currLevel] = seqNo;
    }

    int leftMaxWidth = postorder(node->left, currLevel + 1, seqNo * 2, start, end);
    int rightMaxWidth = postorder(node->right, currLevel + 1, seqNo * 2 + 1, start, end);

    int currWidth = end[currLevel] - start[currLevel] + 1;

    return max(currWidth, max(leftMaxWidth, rightMaxWidth));
}
